#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <memory.h> // for memset
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
#include <stack>
#include <map>

using namespace std;

// 定义二元运算函数指针
typedef double (*binaryOperation)(double, double);
map<char, binaryOperation> opFuncs; // 全局操作符-对应函数映射

namespace ops {
    // + - * / ^
    double add(double a, double b) { return a + b; }
    double minus(double a, double b) { return a - b; }
    double mul(double a, double b) { return a * b; }
    double div(double a, double b) {
        assert(abs(b) > 1e-6); // “除数不为0”
        return a / b;
    }
    double pow(double a, double b) { return pow(a, b); }

    double calc(char op, double a, double b) {
        switch (op) {
            case '+':
                return add(a, b);
            case '-':
                return minus(a, b);
            case '*':
                return mul(a, b);
            case '/':
                return div(a, b);
            case '^':
                return pow(a, b);
            default:
                assert(false);
        }
    }
};

// 抽取给定字符串中出现的第一个浮点数
// 并将指针指向数字后的第一个位置, 存储在next中
// 如: "abc 123.44 xdslja" => 123.44
static int extractNumber(char* str, char** next, double* result) {
    if (!str) {
        return 1;
    }
    char* p = str;
    char buf[32] = {'\0'};
    int i = 0;

    while (!isdigit(*p)) { // 跳过非数学的
        p++;
    }

    if ('\0' == *p) { // 整个串中无数字
        return 2;
    }

    while (isdigit(*p)) { // 小数点前边的数
        buf[i++] = *p++;
    }

    if ('.' == *p) {
        buf[i++] = *p++;
        if (!isdigit(*p)) { // 小数点后无数字
            return 3;
        } else {
            while (isdigit(*p)) {
                buf[i++] = *p++;
            }
        }
    } else if ('\0' != *p && !isblank(*p)) { // 数字后面不是 . 也不是空格
        return 4;
    }
    *next = p;
    *result = atof(buf);
    return 0;
}

// 运算符优先级
int getPriority(char c) {
    switch (c) {
    case '+':
    case '-':
        return 1;
        break;

    case '*':
    case '/':
        return 2;
        break;

    case '^':
        return 3;
        break;

    case '(':
    case ')':
        return 100;

    default: // number
        return 0;
    }
}

// 是否为运算符
bool isOp(char c) {
    const string ops("+-*/^()");
    const int len = ops.length();
    for (int i = 0; i < len; i++) {
        if (c == ops.at(i)) {
            return true;
        }
    }
    return false;
}

// 中缀 转 后缀
int infix2postfix(char infix[], char suffix[]) {
    char*p = infix;
    int i = 0;
    stack<char> s;

    while (*p) {

        // 数字直接输出
        if (isdigit(*p)) {

            suffix[i++] = *p++;
        }

        // 左括号入栈
        else if (*p == '(') {
            s.push(*p++);
        }

        // 右括号, 栈顶的运算符出栈并输出
        // 直到遇到左括号(不输出)
        else if (*p == ')') {
            while (!s.empty() && s.top() != '(') {
                suffix[i++] = s.top();
                s.pop();
                p++;
            }

            if (s.empty()) { // 没有左括号, 非法
                return 1;
            }
            s.pop(); // 左括号出栈, 不输出
        }
    }
    return 0;
}

// 计算后缀表达式的值
int calcPostfix(char* postfix, double* result /* out */) {
    double ret = 0.0;
    char *p = postfix;
    const int NumberSize = 32;
    char number[NumberSize] = {'\0'}; // 用来表示数字
    int i = 0;
    int tmp;
    double tmpNumber;
    stack<double> s;

    // 45 23.8 +
    while (*p != '\0') {
        if (isdigit(*p)) { // 遇到操作数, 暂不支持正负号
            // number[i++] = *p++;
            // while (isdigit(*p)) { // 小数点前边的数字
            //     number[i++] = *p++;
            // }

            // if (*p == '.') {
            //     number[i++] = *p++;
            // } else { // 整数形式
            //     goto labelNumber;
            // }

            // // 小数点后面不是数字
            // if (!isdigit(*p)) {
            //     return 1;
            // }

            // while (isdigit(*p)) {  // 小数点后边的数字
            //     number[i++] = *p++;
            // }
            //

            // extractNumber(char* str, char** next, double* result)
            tmp = extractNumber(p, &p, &tmpNumber);
            if (0 != tmp) {
                return 1;
            }
labelNumber:
            s.push(atof(number));
            i = 0;
            memset(number, 0, NumberSize);
        }

        else if (isOp(*p)) { // 遇到操作符
            if (s.empty()) {
                return 2;
            }
            double b = s.top();
            s.pop();
            double a = s.top();
            s.pop();
            s.push(ops::calc(*p, a, b));
            p++;
        }

        // 空白符跳过
        else if (isblank(*p)) {
            p++;
            continue;
        } else { // 非法字符
            return 3;
        }

    }

    if (s.size() != 1) {
        return 4;
    }

    *result = s.top();
    return 0;
}

static int test() {
    double result = 0;
    char postfix[] = "1 2 + 4 * 2 /"; // ((1+2) * 4) / 2
    int ret = calcPostfix(postfix, &result);
    assert(ret == 0);
    printf("%f\n", result);
    return ret;
}

// 1 + 2 * 3 / 44 - 5
int main(int argc, char const *argv[])
{
    const int BUFFER_SIZE = 256;
    char infix[BUFFER_SIZE] = {'\0'};
    char postfix[BUFFER_SIZE] = {'\0'};
    printf("input infix expression:\n");
    fflush(stdout);
    // scanf("%s", infix);
    printf("%s\n", infix);

    int ret = infix2postfix(infix, postfix);
    assert(ret == 0);
    // double result = calcPostfix(postfix);
    // printf("infix=%f\n", result);

    test();
    return 0;
}
